Global Hypercontractivity on HDX and Applications
September 14, 2022 (GHC 8102)

Abstract: Hypercontractivity is one of the most powerful tools in Boolean function analysis that has many applications in learning theory, probability theory, hardness of approximation and cryptography. Originally studied over the discrete hypercube, recent years have seen increasing interest in extensions to graphs like the p-biased cube, slices of the hypercube and the Grassmann graphs, where a new phenomenon called global hypercontractivity has emerged. In particular, global hypercontractivity on the Grassmann has led to the resolution of Khot’s 2-2 Games Conjecture [KMS’18].

In this work, we develop the theory of global hypercontractivity on high dimensional expanders (HDX). These are an important class of objects that generalize the hypercube and Grassmann graphs, and have recently seen similarly impressive applications in both coding theory and approximate sampling. Our results lead to an understanding of the structure of Boolean functions and a characterization of the non-expanding sets on HDX. This talk is based on the joint work https://arxiv.org/abs/2111.09444. We will cover the necessary background on HDX and hypercontractivity and also discuss some of the applications of global hypercontractivity.